package baidu.d20210907.t3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个字符串，只含大写字母，且长度不超过 11，返回其全排列列表，
 * 列表按字符串从大到小排列，且不包含重复字符。
 *
 * @author habitplus
 * @since 2021-09-07 18:58
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String s = bf.readLine();
        bf.close();

        long st = System.currentTimeMillis();
        ArrayList<String> list = handle(s);
//        System.out.println(list);
        long ed = System.currentTimeMillis();
        System.out.println(ed - st);
    }

    static class E {
        int bit;
        String str;

        public E(int bit, String str) {
            this.bit = bit;
            this.str = str;
        }
    }

    private static ArrayList<String> handle(String s) {
        if (s == null || s.length() == 0)
            return new ArrayList<>();

        int[] m = new int[26];
        for (char c : s.toCharArray()) {
            m[c - 'A'] = 1;
        }

        StringBuilder sb = new StringBuilder();
        int bigBit = 0;
        for (int i = m.length - 1; i >= 0; i--) {
            if (m[i] == 1) {
                sb.append((char) ('A' + i));
                bigBit += (1 << i);
            }
        }

        char[] chs = sb.toString().toCharArray();
        ArrayList<String> ans = new ArrayList<>();
//        bfs(chs, bigBit, ans);
        // 回溯法
        backtrack(chs, bigBit, 0, new StringBuilder(), ans);

//        que.offer("");
//        while (!que.isEmpty()) {
//            for (int i = que.size(); i > 0; i--) {
//                tmp = que.poll();
//                if (tmp.length() == n) {
//                    ans.add(tmp);
//                    continue;
//                }
//
//                for (int j = 0; j < n; j++) {
//                    if (tmp.indexOf(chs[j]) == -1) {
//                        // 不包含当前字符
//                        que.offer(tmp + chs[j]);
//                    }
//                }
//            }
//        }

        return ans;
    }

    private static void backtrack(char[] chs, int bigBit, int cur, StringBuilder tmp, ArrayList<String> ans) {
        if (cur == bigBit) {
            ans.add(tmp.toString());
            return;
        }

        int k;
        for (char c : chs) {
            k = c - 'A';
            if (((cur >> k) & 1) == 0) {
                tmp.append(c);
                backtrack(chs, bigBit, cur | (1 << k), tmp, ans);
                tmp.deleteCharAt(tmp.length() - 1);
            }
        }
    }

    private static void bfs(char[] chs, int bigBit, ArrayList<String> ans) {
        if (chs == null || chs.length == 0) return;

        Queue<E> que = new LinkedList<>();
        int n = chs.length;
        int curBit, k;
        E e;

        que.offer(new E(0, ""));
        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; i--) {
                e = que.poll();
                curBit = e.bit;
                if (bigBit == curBit) {
                    ans.add(e.str);
                    continue;
                }

                for (int j = 0; j < n; j++) {
                    k = chs[j] - 'A';
                    if (((curBit >> k) & 1) == 0) {
                        // 不包含当前字符
                        que.offer(new E(curBit | (1 << k), e.str + chs[j]));
                    }
                }
            }
        }
    }
}
